package cg.studio.algorithm.sort;

import java.util.HashMap;
import java.util.Map;

import org.junit.Test;

import cg.studio.algorithm.HeapUtil;
import cg.studio.practise.Arrays;

public class SortUtil
{

  @Test
  public void testSort()
  {
    testSort( new int[]{ 6,5,4,3,2,1 } );
    testSort( new int[]{ 5, 2,3,4,5 } );
    testSort( new int[]{ 6, 2,3,4,5 } );
    testSort( new int[]{ 5, 2, 6,6,7,5 } );
  }
  
  protected void testSort( int[] values )
  {
    Arrays.printArray( values );
    System.out.println();
    {
      int[] clone = values.clone();
      quickSort( clone );
      if( !isSortedArray( values, clone ) )
      {
        System.out.print( "quickSort:   \t" );
        Arrays.printArray( clone );
        System.out.println();
      }
    }
    {
      int[] clone = values.clone();
      quickSort_1( clone );

      if( !isSortedArray( values, clone ) )
      {
        System.out.print( "quickSort_1: \t" );
        Arrays.printArray( clone );
        System.out.println();
      }
    }
    {
      int[] clone = values.clone();
      quickSort_2( clone );
      if( !isSortedArray( values, clone ) )
      {
        System.out.print( "quickSort_2: \t" );
        Arrays.printArray( clone );
        System.out.println();
      }
    }
    {
      int[] clone = values.clone();
      insertionSort( clone );
      if( !isSortedArray( values, clone ) )
      {
        System.out.print( "insertionSort: \t" );
        Arrays.printArray( clone );
        System.out.println();
      }
    }
    {
      int[] clone = values.clone();
      mergeSort( clone );
      if( !isSortedArray( values, clone ) )
      {
        System.out.print( "mergeSort:    \t" );
        Arrays.printArray( clone );
        System.out.println();
      }
    }
    {
      int[] clone = values.clone();
      mergeSort_recursive( clone );
      if( !isSortedArray( values, clone ) )
      {
        System.out.print( "mergeSort_rec: \t" );
        Arrays.printArray( clone );
        System.out.println();
      }
    }
    {
      int[] clone = values.clone();
      bubbleSort( clone );

      if( !isSortedArray( values, clone ) )
      {
        System.out.print( "bubbleSort:    \t" );
        Arrays.printArray( clone );
        System.out.println();
      }
    }
    {
      int[] clone = values.clone();
      selectionSort( clone );
      Arrays.printArray( clone );
      System.out.println();
      if( !isSortedArray( values, clone ) )
      {
        System.out.print( "selectionSort:    \t" );
        Arrays.printArray( clone );
        System.out.println();
      }
    }
    {
      int[] clone = values.clone();
      heapSort( clone );
      Arrays.printArray( clone );
      System.out.println();
      if( !isSortedArray( values, clone ) )
      {
        System.out.print( "heapSort:    \t" );
        Arrays.printArray( clone );
        System.out.println();
      }
    }
    
    
    System.out.println();
  }
  
  
  public static void quickSort( int[] values )
  {
    if( values == null )
      throw new IllegalArgumentException( "values is null." );
    if( values.length <= 1 )
      return;
    quickSort( values, 0, values.length-1 );
  }
  
  /**
   * sort the sub-array of values, start with <start> inclusive and end with <end> inclusive
   * divide rule: value larger than comparing value, move to the right; else, move to the left, 
   *   namely, left are value less or equal to the comparing value
   * use (leftValue+rightValue)/2 as comparing value
   * @param values
   * @param start
   * @param end
   */
  public static void quickSort( int[] values, int start, int end )
  {
    if( end == start )
      return;
    
    //swap
    int comparing = getComparingValue( values, start, end );
    int left = start;
    int right = end;
    
    while( left < right )
    {
      //find value larger than comparing from left
      for( ; left<right; ++left )
      {
        if( values[ left ] > comparing )
          break;
      }
      for( ; right > left; --right )
      {
        if( values[ right ] <= comparing )
          break;
      }

      if( left != right )
      {
        //swap left and right
        int tmp = values[ left ];
        values[left] = values[right];
        values[right] = tmp;

        //for next loop
        ++left;
        --right;
      }
    }
    
    //move at least one item in case infinite loop
    while( left>start && values[left] >= comparing )
      --left;
    
    quickSort( values, start, left );
    quickSort( values, left+1, end );
  }
  
  protected static int getComparingValue( int[] values, int start, int end )
  {
    return (values[start]+values[end])/2;
  }
  

  public static void quickSort_1( int[] arr )
  {
    quickSort_1( arr, 0, arr.length - 1 );
  }

  /**
   * choose first value as the comparing value
   * @param arr
   * @param start
   * @param end
   */
  public static void quickSort_1( int[] arr, int start, int end )
  {
    if ( end <= start )
      return;

    int compare = arr[start];

    int left = start + 1;
    int right = end;

    while ( left < right )
    {
      for ( ; left < right; ++left )
      {
        if ( arr[left] > compare )
          break;
      }

      for ( ; right > left; --right )
      {
        if ( arr[right] <= compare )
          break;
      }

      if ( right > left )
      {
        // swap
        int tmp = arr[left];
        arr[left] = arr[right];
        arr[right] = tmp;

        left++;
        right--;
      }
    }
    
    //left == right, should handle this item
    if( arr[left] > compare )
      --left;
    //prevent the first one is the largest one
    if( left == end )
    {
      //switch first with the last one
      int tmp = arr[start];
      arr[start] = arr[end];
      arr[end] = tmp;
      --left;
    }
    
    quickSort_1( arr, start, left );
    quickSort_1( arr, left + 1, end );
  }
  
  
  void quickSort_2( int values[] )
  {
    quickSort_2( values, 0, values.length-1 );
  }
  /**
   * prefer this method:
   *   - when compare: use < and > instead of ( <= and > ) or ( < and >= ), 
   *     this way, can make sure left and right will not out of bound ( as min(values) <= compare <= max( values )
   *   - the while condition and left++/right-- is ( left<=right ) instead of ( left<right ), 
   *     which make sure no any value not compared, and right < left at last.
   * @param values
   * @param start
   * @param end
   */
  void quickSort_2( int values[], int start, int end )
  {
    int left = start, right = end;
    int compare = getComparingValue( values, start, end );//values[( start + end ) / 2];

    while ( left <= right )
    {
      while ( values[left] < compare )
        left++;
      while ( values[right] > compare )
        right--;
      if ( left <= right )
      {
        if( left < right )
        {
          int tmp = values[left];
          values[left] = values[right];
          values[right] = tmp;
        }
        left++;
        right--;
      }
    }
    
    if ( right > start  )
      quickSort_2( values, start, right );
    if ( left < end )
      quickSort_2( values, left, end );
  }

  /**
   * select a value and insert into a right place
   * @param values
   */
  public static void insertionSort( int[] values )
  {
    if( values == null )
      throw new IllegalArgumentException( "values is null." );
    if( values.length <= 1 )
      return;
    
    for( int selectIndex=1; selectIndex < values.length; ++selectIndex )
    {
      int selectValue = values[selectIndex];
      
      //move data
      int i=selectIndex-1;
      for( ; i>=0 && values[i] > selectValue; --i )
      {
        values[i+1] = values[i];
      }
      values[i+1] = selectValue;
    }
    
    
  }

  /**
   * find where the compareValue should put to
   * return start if less than all, return end+1 if larger than all  
   * @param values
   * @param start
   * @param end
   * @param compareValue
   * @return
   */
  public static int findInsertIndex( int[] values, int start, int end, int compareValue )
  {
    if( compareValue <= values[start] )
      return start;
    if( compareValue >= values[end] )
      return end+1;
    if( end - start == 1 )
      return start+1;
    int index = start + ( end-start )/2;
    if( compareValue == values[index] )
      return index;
    if( compareValue < values[index] )
      return findInsertIndex( values, start, index-1, compareValue );
    return findInsertIndex( values, index+1, end, compareValue );
  }
  
  public static void mergeSort( int[] values )
  {
    if( values == null )
      throw new IllegalArgumentException( "values is null." );
    if( values.length <= 1 )
      return;
    
    for( int stepLen=1; stepLen<values.length; stepLen *= 2 )
    {
      for( int i=0; i<values.length-1; i+=stepLen*2 )
      {
        merge( values, i, i+stepLen-1, i+stepLen, i+stepLen+stepLen-1 );
      }
    }
  }
  
  /**
   * merge two sorted sub-array
   * @param values
   * @param start1 start1 should less than start2
   * @param end1 end1 should less than start2, it is possible end1 out of the bounds 
   * @param start2
   * @param end2 end2 is possible to great than values.length-1, should check 
   */
  public static void merge( int[] values, int start1, int end1, int start2, int end2 )
  {
    assert( start1 < start2 );

    if( start2 > values.length-1 )
      return;
    int[] clonedValue = java.util.Arrays.copyOfRange( values, start1, end1+1 );
    int i=0;  //clonedValue
    int j=start2;
    for( int dstIndex=start1; i<clonedValue.length; ++dstIndex )
    {
      if( j <= end2 && j<values.length && values[j] < clonedValue[i]  )
      {
        values[dstIndex] = values[j];
        j++;
      }
      else
      {
        values[dstIndex] = clonedValue[i];
        i++;
      }
    }
  }
  
  public static void mergeSort_recursive( int[] values )
  {    
    if( values == null )
      throw new IllegalArgumentException( "values is null." );
    if( values.length <= 1 )
      return;
    mergeSort_recursive( values, 0, values.length-1 );
  }
  
  /**
   * 
   * @param values
   * @param start start index, inclusive
   * @param end end index, inclusive
   */
  public static void mergeSort_recursive( int[] values, int start, int end )
  {
    if( start == end )
      return;
    int middle = (end+start)/2;
    mergeSort_recursive( values, start, middle );
    mergeSort_recursive( values, middle+1, end );
    
    //merge
    merge( values, start, middle, middle+1, end );
  }
  
  public static void bubbleSort( int[] values )
  {
    for( int sortedLen = 0; sortedLen < values.length-1; ++sortedLen )
    {
      for( int j=0; j<values.length-sortedLen-1; ++j )
      {
        if( values[j] > values[j+1] )
        {
          //swap
          int tmp = values[j];
          values[j] = values[j+1];
          values[j+1] = tmp;
        }
      }
    }
  }
  
  /**
   * selected the min value from unsorted and add to the end of sorted sub-array
   * @param values
   */
  public static void selectionSort( int[] values )
  {
    for( int sortedLen = 0; sortedLen < values.length-1; ++sortedLen )
    {
      int minValueIndex = sortedLen;
      for( int i=sortedLen+1; i<values.length; ++i )
      {
        if( values[i] < values[minValueIndex] )
          minValueIndex = i;
      }
      
      //swap minValueIndex with sortedLen
      int tmp = values[sortedLen];
      values[sortedLen] = values[ minValueIndex ];
      values[minValueIndex] = tmp;
    }
  }
  
  public static void heapSort( int[] values )
  {
    HeapUtil.buildMaxHeap( values );
    
    for( int heapSize = values.length; heapSize > 1; HeapUtil.maxHeapify( values, --heapSize, 0 ) )
    {
      //swap 0 with heapSize-1
      int tmp = values[0];
      values[0] = values[ heapSize-1 ];
      values[ heapSize-1 ] = tmp;
    }
  }
  
  public static void buildMaxHeap( int[] values )
  {
    
  }
  
  public static void treeSort( int[] values )
  {
    
  }
  
  public static boolean isSortedArray( int[] orgArr, int[] sortedArr )
  {
    if( orgArr.length != sortedArr.length )
      return false;
    // Value ==> count
    Map< Integer, Integer > orgMap = new HashMap< Integer, Integer >();
    Map< Integer, Integer > sortedMap = new HashMap< Integer, Integer >();
    for( int i=0; i<orgArr.length; ++i )
    {
      addValueCount( orgMap, orgArr[i] );
      addValueCount( sortedMap, sortedArr[i] );
    }
    
    //values are same
    if( !orgMap.equals( sortedMap ) )
      return false;
    
    //sortedArr is sorted, ascending order
    for( int i=0; i<sortedArr.length-1; ++i )
    {
      if( sortedArr[i] > sortedArr[i+1] )
        return false;
    }
    return true;
  }
  
  protected static void addValueCount( Map< Integer, Integer > map, int value )
  {
    Integer count = map.get( value );
    if( count == null )
    {
      count = 1; 
    }
    else
    {
      count++;
    }
    map.put( value, count );
  }
}
